//给你一个由 X-Y 平面上的点组成的数组 points ，其中 points[i] = [xi, yi] 。从其中取任意三个不同的点组成三角形，返回能组成的
//最大三角形的面积。与真实值误差在 10⁻⁵ 内的答案将会视为正确答案。 
//
// 
//
// 示例 1： 
// 
// 
//输入：points = [[0,0],[0,1],[1,0],[0,2],[2,0]]
//输出：2.00000
//解释：输入中的 5 个点如上图所示，红色的三角形面积最大。
// 
//
// 示例 2： 
//
// 
//输入：points = [[1,0],[0,0],[0,1]]
//输出：0.50000
// 
//
// 
//
// 提示： 
//
// 
// 3 <= points.length <= 50 
// -50 <= xi, yi <= 50 
// 给出的所有点 互不相同 
// 
//
// Related Topics 几何 数组 数学 👍 212 👎 0


package LeetCode.editor.cn;

/**
 * @author ldltd
 * @date 2025-09-27 09:50:39
 * @description 812.最大三角形面积
 */
public class LargestTriangleArea{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 LargestTriangleArea fun=new LargestTriangleArea();
	 	 Solution solution = fun.new Solution();

	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
		 // 海伦公式
	public double largestTriangleArea1(int[][] points) {
		double ans=0.0;
		for(int i=0;i<points.length;i++){
			for(int j=i+1;j<points.length;j++){
				for(int k=j+1;k<points.length;k++){
					ans=Math.max(ans,countArea(points[i],points[j],points[k]));
				}
			}
		}
		return ans;
	}
	//S=√p(p-a)(p-b)(p-c)，其中p=(a+b+c)/2
	public double countArea(int d1[],int d2[],int d3[]){
		// 计算边长，勾股定理
		double a=Math.sqrt((d1[0]-d2[0])*(d1[0]-d2[0])+(d1[1]-d2[1])*(d1[1]-d2[1]));
		double b=Math.sqrt((d1[0]-d3[0])*(d1[0]-d3[0])+(d1[1]-d3[1])*(d1[1]-d3[1]));
		double c=Math.sqrt((d3[0]-d2[0])*(d3[0]-d2[0])+(d3[1]-d2[1])*(d3[1]-d2[1]));
		double p=(a+b+c)/2.0;
		return Math.sqrt(p*Math.abs(p-a)*Math.abs(p-b)*Math.abs(p-c));
	}
	//向量点积
	public double largestTriangleArea(int[][] points) {
		double ans=0;
		for(int i=0;i<points.length;i++){
			for(int j=i+1;j<points.length;j++){
				for(int k=j+1;k<points.length;k++){
					ans=Math.max(ans,crossProduct(points[i],points[j],points[k]));
				}
			}
		}
		return ans;
	}
	public double crossProduct(int d1[],int d2[],int d3[]){
		int a[]={d2[0]-d1[0],d2[1]-d1[1]},b[]={d3[0]-d1[0],d3[1]-d1[1]};
		return Math.abs(a[0]*b[1]-a[1]*b[0])/2.0;
	}
}
//leetcode submit region end(Prohibit modification and deletion)

}
